Electrical Engineering-Systems Dept.

*** SEMINAR ***

Ohn Tsarfati

(M.Sc. student under the supervision of Prof. Yair Be’ery)

on the subject:

Parallel MDRR Scheduling Algorithms for Many-Core Architectures

The Traffic Scheduler is an important unit within today’s switches and routers. This unit is responsible for scheduling packets from back-logged queues to the output ports. Its correctness and speed matter the most in cases of contention – when two or more packets from different queues are competing for the same output port (Head of Line blocking scenario). The Traffic Scheduler is required to decide which input to serve in a very short period of time, and in a way that satisfies the constraints that are dictated by the user (typically the ISPs – Internet Service Providers).

Today’s high-speed Traffic Schedulers solutions are implemented in hardware (ASIC) devices, which have low or no flexibility for changes in the scheduling parameters and methods. Software implementations are flexible although they require a very strong (therefore expensive) processor platform to support the high bandwidth.

In this thesis work we present several software implementations of the common Traffic Scheduler, the MDRR, over three many-core platforms (Intel’s Single-chip Cloud Computer (SCC), Tilera’s TilePRO64 and IBM’s PowerEN). These platforms have high processing power, comparing to their cost and their power consumption. A Traffic Scheduler implemented using a many-core is also enjoying the flexibility of a software product.

The highest performance observed was over Tilera’s TilePRO64 device, using a novel parallel algorithm that utilizes the inter-core network and the cores themselves to create several systolic arrays within the chip. This algorithm achieved a bandwidth of 60.7 Gigabits per second, using 57 cores, for a full traffic load. The speedup factor was 121.79 (super-linear speedup) and the input was a scheduling tree with 4,681 nodes.